package y_2025.m04.d11.t04;

import java.util.Scanner;

public class MatrixChain {
    static int[] A; // 矩阵规模
    static int[][] m; // 最优解
    static int[][] s; // 分割点

    static void MatrixChain(int n) {
        // 初始化对角线
        for (int i = 0; i <= n; i++) {
            m[i][i] = 0;
        }

        // r个矩阵连乘
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                m[i][j] = m[i][i] + m[i + 1][j] + A[i - 1] * A[i] * A[j];
                s[i][j] = i;

                // 变换分隔位置，逐一测试
                for (int k = i + 1; k < j; k++) {
                    int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
    }

    static void print(int i, int j) {
        if (i == j) {
            System.out.print("A[" + i + "]");
            return;
        }
        System.out.print("(");
        print(i, s[i][j]);
        print(s[i][j] + 1, j); // 修正递归索引
        System.out.print(")");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入矩阵的数量 n: ");
        int n = scanner.nextInt();

        A = new int[n + 1];
        m = new int[n + 1][n + 1];
        s = new int[n + 1][n + 1];

        System.out.println("请输入每个矩阵的维度（共 " + n + " 个数字）：");
        for (int i = 0; i <= n; i++) {
            A[i] = scanner.nextInt();
        }

        MatrixChain(n);
        System.out.print("最佳添加括号的方式为：");
        print(1, n);
        System.out.println("\n最小计算量的值为：" + m[1][n]);

        scanner.close();
    }
}